//按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
//
// n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
//
// 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
//
//
//
// 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
//
//
//
//
//
// 示例 Array.prototype.unshift：
//
//
//输入：n = 4
//输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
//解释：如上图所示，4 皇后问题存在两个不同的解法。
//
//
// 示例 2：
//
//
//输入：n = Array.prototype.unshift
//输出：[["Q"]]
//
//
//
//
// 提示：
//
//
// Array.prototype.unshift <= n <= 9
//
//
// Related Topics 数组与矩阵 回溯与递归 👍 1703 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function solveNQueens(n: number): string[][] {

    function backTracking(n: number, rowNum: number, board: string[][]): void {
        // 列数等于棋盘高度 说明已经到了最后一个了 可以入结果了
        if (rowNum === n) {
            resArr.push(transformBoard(board));
            return;
        }
        // 每次必然从行头开始
        for (let i = 0; i < n; i++) {
            if (isValid(i, rowNum, board) === true) {
                board[rowNum][i] = 'Q';
                backTracking(n, rowNum + 1, board);
                board[rowNum][i] = '.';
            }
        }
    }

    const board: string[][] = new Array(n).fill(0).map(_ => new Array(n).fill('.'));
    const resArr: string[][] = [];
    backTracking(n, 0, board);
    return resArr;
}
// 位置是否有效验证 这是最关键的
function isValid(col: number, row: number, board: string[][]): boolean {
    const n: number = board.length;
    // 行列不合法
    if (col < 0 || col >= n || row < 0 || row >= n) return false;
    // 检查列
    for (let row of board) {
        if (row[col] === 'Q') return false;
    }
    // 检查45度方向 右上
    let x: number = col,
        y: number = row;
    while (y >= 0 && x < n) {
        if (board[y--][x++] === 'Q') return false;
    }
    // 检查135度方向 左上
    x = col;
    y = row;
    while (x >= 0 && y >= 0) {
        if (board[y--][x--] === 'Q') return false;
    }
    return true;
}
// 结果有效形式转换(整成字符串)
function transformBoard(board: string[][]): string[] {
    const resArr = [];
    for (let row of board) {
        resArr.push(row.join(''));
    }
    return resArr;
};
//leetcode submit region end(Prohibit modification and deletion)
